1. Field of the Invention
The present invention relates to a method and apparatus for allocating bandwidth at a switch in an asynchronous transfer mode network.
2. Art Background
Asynchronous transfer mode (ATM) networks have achieved widespread popularity. Briefly, an ATM network consists of switches interconnected by links to form configurable networks between source and destination devices. The switches route cells of data which are 53 bytes in length. The cells are routed across a virtual circuit (VC) established between the source device and a destination device. Each virtual circuit is composed of one or more links and switches. A link or a switch is not exclusive to a single virtual circuit; multiple virtual circuits can be routed across a single link. The resources available, for example, the bandwidth of the switch or link, are limited by the physical constraints of the network. Thus, the network must provide a way to allocate network resources so that the capacity of the elements, e.g., the links, is not exceeded.
In circuit switched computer networks (both actual and virtual circuit switching) it is advantageous for applications to make resource reservations ahead of time. This will guarantee the application operating on the source/destination device the resources it requires. Such a reservation requires that the applications be able to estimate ahead of time their resource requirements. While this knowledge is typically available to audio or video communication applications, this information typically is not known to other data applications (this includes existing applications which were not designed to predict or state in advance their resource requirements as well as applications that inherently cannot predict their usage patterns). Therefore, a different mechanism is required in order to provide service to such applications.
Thus, network usage is divided into two classes--applications that do and applications that do not state resource requirements in advance. Those applications that will state their requirements in advance are guaranteed those resources (subject to their availability at the time the reservation is made). The remaining applications will have to share the remaining available bandwidth. These VCs are referred to as available bit rate (ABR) VCs. The problem with ABR VCs is to determine what network resources are available and how to share the available resources among the applications that request the resources in a way that is both fair to the users and efficient for the network. Thus, fairness, high link utilization and fast response to congestion conditions are desired features of such mechanisms.
Congestion can occur when the total input rate or bandwidth of VCs that traverse a given link is greater than the available link capacity. As a result, buffers to the links of the switches may overflow and cells may be dropped. For ABR VCs, congestion conditions typically occur due to a time difference between the moment cells are released by a device into the network and the moment feedback is received regarding the state of the network resulting from this and other cell traffic.
One simple approach to perform flow control is by using an Explicit Flow Control Indicator (EFCI). An application at the source device adapts the rate at which cells are transmitted according to a single congestion bit generated by the network or destination device. The source device increases the rate when no congestion indication is received, and decreases the rate upon the reception of an indication of congestion. Such a mechanism does not result in a fair allocation of the resources among the requesting users (due to the "beat down effect" in which cells from VCs that pass through many switches are more likely to be marked with a congestion indication than cells from VCs that pass through fewer switches), and may also cause severe fluctuations between congested and not congested states.
A better method to control congestion is to inform the source device to adjust the rate in order to match the available link capacity. The available link capacity can change as a result of establishment and termination of VCs as well as changes in network usage that are inherent in the statistical nature of network behavior. This type of method attempts to control congestion to achieve high utilization of the available link capacity while sharing the available bandwidth capacity in a fair manner.
The general approach is for devices that do not explicitly state their bandwidth requirement to issue an Available Bit Rate (ABR) request to the network alerting the network to their existence. The network will then, from time to time, inform each device of its current share of the available bandwidth. The user must then obey (i.e., not exceed) its currently assigned rate.
One structure for administering flow control is described in A. F. Bonomie, K. W. Fendick, "Rate-Based Flow Control for ATM Networks", IEEE Network (March/April 1995) pp. 25-39. In the mechanism described, a network source device is required to send from time to time special resource management (RM) cells for every virtual circuit for which this device is the source. RM cells transmitted by the source device are referred to as forward RM cells (FRM). These RM cells traverse the links and switches of the virtual circuit from source device to destination device, possibly gathering information on the way. Once the FRM cell reaches the destination, the cell is sent back to the source device, again with possible computations regarding resource allocation performed on the way. The FRM cells turned around at the destination device of the virtual circuit and sent back to the source device are referred to as backward RM cells (BRM). When the BRM cell finally reaches the source device, the cell contains the desired feedback information regarding the bandwidth available for that virtual circuit. The source device can then update the current transmission rate for that virtual circuit based upon the feedback information.
Advanced flow control approaches fall into the category of an explicit rate flow control mechanism in which each device is fed back an explicit quantitative indication of the amount of bandwidth that is available for every virtual circuit originating in that device. Explicit rate algorithms must perform three important functions:
1. Determine the load in the various links and routes of the network. PA1 2. Compute the fair share of the bandwidth for a virtual circuit. PA1 3. Determine the actual (explicit) rate or bandwidth for each virtual circuit and feed the rate back to the source of the virtual circuit.
To be useful, these rate algorithms must be fast in order to provide accurate and timely information. In order to meet the above requirements, the algorithms should be distributed and implemented in hardware, not executed centrally for all switches and not involve the programmable switch controller in the process.
A crucial factor in the design of a flow control mechanism is the definition and determination of fair share. The fair share value is used to determine how much bandwidth a particular virtual circuit is allocated. The most commonly used criterion for fairness is referred to as the Max-Min allocation. This method allocates the resources such that applications that require little of the network (below some minimum bandwidth value) receive whatever is requested, whereas applications requiring more resources equally share in the rest of the resources. A unique property of this allocation is that no rate increase of a given virtual circuit is possible without a corresponding decrease of the rate of another virtual circuit with equal or smaller allocation of bandwidth.
The rate of convergence also is important in flow control. A time gap exists between when the time data (e.g., an FRM cell) is inserted into the network and the time feedback (via, for example, a BRM cell) regarding the effect of this data is fed back to the source device. More particularly, there is a time lag from the time a source sends cells out on the network and the time the source receives resource allocation information back regarding modification of the bandwidth in accordance with the resources available. This delay causes temporary inaccuracies in the allocation and renders the network vulnerable to congestion problems. Consequently, it is crucial that the explicit rate algorithm converges fast to a final state. For example, when the available bandwidth is reduced, rapid convergence minimizes the potential of congestion and when the available bandwidth is increased rapid convergence likewise increases network utilization.